#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "time.h"
#define M 1024
#define maxsize 10000
int main()
{
	freopen("data.txt","r",stdin);
	int i,n,m,max,min,k,p;
	int a[maxsize];
	int head[maxsize];
	int end[maxsize];
	int link[maxsize];
	double star,finish;

	printf("please input the number of sequence:");
	scanf("%d",&n);
	printf("please input a disorderly sequence:");
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}	
    	star=(double)clock();
	printf("\n");
	max=a[n-1];min=a[0];
	for(i=n-1;i>=0;i--)
	{
		if(a[i]>max)max=a[i];
	}
	for(i=0;i<n;i++)
	{
		if(a[i]<min)min=a[i];
	}
	m=max-min;
	for(i=0;i<=m;i++)
	{
		head[i]=-1;
		end[i]=-1;
	}
	for(i=0;i<n;i++)
	   link[i]=-1;
	for(i=0;i<n;i++)
	{
		k=a[i]-min;
		if(head[k]==-1)
		{
			head[k]=i;
			end[k]=i;
		}
		else
		{
			link[end[k]]=i;end[k]=i;
		}
	}
	printf("\nresult is:\n");
	for(i=0;i<=m;i++)
	{
		if(head[i]!=-1)
		{
			if(head[i]==end[i])
			{
				p=head[i];
				printf("%d,",a[p]);
			}
			else
			{
				p=head[i];
				do{
					printf("%d,",a[p]);
					p=link[p];
				}while(link[p]!=0);
			}
		}
		else continue;
	}
	
    printf("\n");
    for(i=0;i<M;i++)finish=(double)clock();
    printf("The time is:%.2fms\n",(finish-star));
}
